/* 
 * Binary Tree Maximum Path Sum
 */

#include "../../func.h"

int maxPathSum(TreeNode *root)
{
    dfs(root);
}

int max_sum = INT_MIN;
int dfs(TreeNode *root)
{
    if (nullptr == root)
        return 0;
    int l = dfs(root->left);
    int r = dfs(root->right);
    int sum = root->val;
    if (l > 0)
        sum += l;
    if (r > 0)
        sum += r;
    max_sum = max(max_sum, sum);
    return max(r, l) > 0 ? max(r, l) + root->val : root->val;
}